package Q442

import java.util.ArrayList




/**
 * 数组中重复的数据
 * @author 23737
 * @date 2022.5.8
 */
class Main {

}

fun main() {
    val array = intArrayOf(4, 3, 2, 7, 8, 2, 3, 1)
    println(Solution().findDuplicates(array))
}

class Solution {
    fun findDuplicates(nums: IntArray): List<Int> {
        val res: MutableList<Int> = ArrayList<Int>()
        if (nums.isEmpty()) return res
        val map = HashMap<Int, Int>()
        for (num in nums) {
            if (map[num] == 1) {
                res.add(num)
            } else {
                map.put(num, map.getOrDefault(num, 0) + 1)
            }
        }
        return res
    }

    fun findDuplicates2(nums: IntArray): List<Int>? {
        val ret: MutableList<Int> = ArrayList()
        val n = nums.size
        for (i in 0 until n) {
            nums[(nums[i] - 1) % n] += n
        }
        for (i in 0 until n) {
            if (nums[i] > 2 * n) ret.add(i + 1)
        }
        return ret
    }
}